/**
 * 
 */
package com.dalonedrau.graph;

import java.util.ArrayList;
import java.util.List;

/**
 * @author Donald
 *
 */
public class IndexedPriorityQLow {
	private float[] vecKeys;
    private int[] m_Heap;
    private int[] m_invHeap;
    private int m_iSize;
    private int m_iMaxSize;

    public IndexedPriorityQLow(final float[] keys, int MaxSize)
    {
        vecKeys = keys;
        m_iMaxSize = MaxSize;

        m_iSize = 0;

        int capacity = MaxSize + 1;

        m_Heap = new int[capacity];
        m_invHeap = new int[capacity];

        for (int i = 0; i < capacity; i++)
        {
            m_Heap[i] = 0;
            m_invHeap[i] = 0;
        }
    }

    public boolean empty() {
        return (m_iSize == 0);
    }
  //to insert an item into the queue it gets added to the end of the heap
    //and then the heap is reordered from the bottom up.
    public void insert(int idx)
    {
       ++m_iSize;

        m_Heap[m_iSize] = idx;

        m_invHeap[idx] = m_iSize;

        ReorderUpwards(m_iSize);
    }

    //to get the min item the first element is exchanged with the lowest
    //in the heap and then the heap is reordered from the top down. 
    public int pop() {
        swap(1, m_iSize);

        ReorderDownwards(1, m_iSize - 1);

        return m_Heap[m_iSize--];
    }

    //if the value of one of the client key's changes then call this with 
    //the key's index to adjust the queue accordingly
    public void changePriority(final int idx) {
        ReorderUpwards(m_invHeap[idx]);
    }

    private void swap(final int a, final int b) {
        int temp = m_Heap[a];
        m_Heap[a] = m_Heap[b];
        m_Heap[b] = temp;

        //change the handles too
        m_invHeap[m_Heap[a]] = a;
        m_invHeap[m_Heap[b]] = b;
    }
    private void ReorderUpwards(int nd) {
        //move up the heap swapping the elements until the heap is ordered
        while ((nd > 1) 
        		&& (vecKeys[m_Heap[nd / 2]] > vecKeys[m_Heap[nd]])) {
            swap(nd / 2, nd);
            nd /= 2;
        }
    }
    private void ReorderDownwards(int nd, int HeapSize) {
        //move down the heap from node nd swapping the elements until
        //the heap is reordered
        while (2 * nd <= HeapSize) {
            int child = 2 * nd;

            //set child to smaller of nd's two children
            if ((child < HeapSize) 
            		&& vecKeys[m_Heap[child]] > vecKeys[m_Heap[child + 1]]) {
                ++child;
            }

            //if this nd is larger than its child, swap
            if (vecKeys[m_Heap[nd]] > vecKeys[m_Heap[child]]) {
                swap(child, nd);

                //move the current node down the tree
                nd = child;
            } else {
                break;
            }
        }
    }
}
